Thuật toán Fleury Đồ thị Euler

Ta có thể vạch được 1 chu trình Euler trong đồ thị liên thông (G) có bậc của mọi đỉnh là chẵn theo thuật toán Fleury sau:

Xuất phát từ 1 đỉnh bất kỳ của đồ thị (G) và tuân theo 2 quy tắc sau:
  1. Mỗi khi đi qua một cạnh nào đó thì xóa nó đi, sau đó xóa đỉnh cô lập (nếu có).
  2. Không bao giờ đi qua cầu trừ khi không còn cách đi nào khác.

Thuật toán

Cho G = (V, E) là một đồ thị Euler.

  • Bước 1. Bắt đầu với i = 0 và định nghĩa T0 = v0.
  • Bước 2.
    • Đặt Ti = v0e1v1e2…eiviei là đường đi giữa v0 và vi tại bước thứ i, gọi Ei = {e1, e2, …, ei}; G’ là đồ thị con sau khi xóa các cạnh thuộc Ei trong G: G’= G – Ei.
    • Chọn một cạnh ei+1 nối vi với vi+1 từ tập cạnh E – Ei. Lưu ý là nếu ei+1 là một cạnh cầu trong đồ thị con G’, chỉ chọn nó khi và chỉ khi không còn lựa chọn nào khác.
    • Cập nhật Ti+1 = Tiei+1vi+1 = v0e1v1e2…eiviei+1vi+1. Nếu không còn lựa chọn nào cho cạnh ei+1 thì dừng.
  • Bước 3. Gán i = i + 1, quay lại bước 2.

Ví dụ

Tìm chu trình Euler

Hình 8: Ví dụ: Tìm chu trình Euler

Bước 1: Xuất phát từ (1) có thể đi theo cạnh (1,2) hoặc (1,6), giả sử là cạnh (1,2) (xóa cạnh (1,2))

Hình 9: Tìm chu trình Euler_Bước 1

Bước 2: Từ (2) có thể đi qua một trong các cạnh (2,3), (2,6), (2,5), giả sử là cạnh (2,3) (xóa cạnh (2,3)).

Hình 10: Tìm chu trình Euler_Bước 2

Bước 3: Tiếp tục, từ (3) có thể đi qua một trong các cạnh (3,4), (3,7), (3,8), giả sử là cạnh (3,4) (xóa cạnh (3,4)).

Hình 11: Tìm chu trình Euler_Bước 3

Bước 4: Từ (4), đi theo cạnh (4,7) (xóa (4,7) và đỉnh (4)).

Hình 12: Tìm chu trình Euler_Bước 4

Bước 5: Vì (7,6) là cầu nên có thể đi theo một trong hai cạnh (7,3), (7,8), giả sử (7,3) (xóa (7,3)).

Hình 13: Tìm chu trình Euler_Bước 5

Bước 6: Đi theo (3,8) (xóa (3,8) và đỉnh (3)).

Hình 14: Tìm chu trình Euler_Bước 6

Bước 7: Đi theo (8,7) (xóa (8,7) và đỉnh (8)).

Hình 15: Tìm chu trình Euler_Bước 7

Bước 8: Tiếp tục đi theo cạnh (7,6) (xóa (7,6) và đỉnh (7)).

Hình 16: Tìm chu trình Euler_Bước 8

Bước 9: Vì (6,1) là cầu nên đi theo cạnh (6,2) hoặc (6,5), giả sử (6,2) (xóa (6,2)).

Hình 17: Tìm chu trình Euler_Bước 9

Bước 10: Tiếp tục đi theo (2,5) (xóa (2,5) và đỉnh (2)).

Hình 18: Tìm chu trình Euler_Bước 10

Bước 11: Theo cạnh (5,6) (xóa cạnh (5,6) và đỉnh (5)).

Hình 19: Tìm chu trình Euler_Bước 11

Bước 12: Cuối cùng đi theo cạnh (6,1) (xóa cạnh (6,1), đỉnh (6) và đỉnh (1)).Như vậy, trong ví dụ trên đã tìm được 1 chu trình Euler:

1 - 2 - 3 - 4 - 7 - 3 - 8 - 7 - 6 - 2 - 5 - 6 - 1

Cài đặt thuật toán Fleury

Ta sẽ cài đặt thuật toán Fleury trên một đồ thị vô hướng. Ta coi đồ thị này đã có chu trình Euler, công việc của ta là tìm ra chu trình đó thôi. (Đồ thị đã có tính liên thông và mọi đỉnh đều có bậc chẵn).[1]

  • Input: file văn bản input.txt
    • Dòng 1: Chứa số đỉnh n của đồ thị
    • Các dòng tiếp theo là ma trận kề của đồ thị
  • Output: file văn bản output.txt, ghi chu trình Euler.
Hình 19: Ví dụ thuật toán Fleury

Tập tin input.txt:

Hình 20: Tập tin input.txt
  1 #include <iostream>  2 #include <fstream>  3 #include <string>  4 #include <vector>  5 using namespace std;  6   7 ifstream infile("input.txt");  8 ofstream outfile("output.txt");  9 bool euler(vector<vector<int> > edge); 10 bool fleury(vector<vector<int> > edge, vector<int> del); 11 vector<vector<int> >erase(vector<vector<int> > edge, vector<int> del); 12 bool empty(vector<vector<int> > edge); 13  14 int main(){	 15 	int n, i, j; 16 	//đọc ma trận từ file input.txt 17 	infile>>n; 18 	vector<vector<int> > edge; int val; 19 	for(i=0; i<n; i++){ 20 		vector<int> row; 21 		for(j=0; j<n; j++) 22 		{ 23 			infile>>val; 24 			row.push_back(val); 25 		} 26 		edge.push_back(row); 27 	}	 28 	if(euler(edge)){ 29 		cout<<"Chu trinh Euler: "<<endl; 30 		vector<int> circuit; int current=0; 31 		circuit.push_back(current); 32 		cout<<current + 1<<" "; 33 		while(!empty(edge)){ 34 			for(i=0; i<n; i++){ 35 				int previous=current; 36 				if(edge[current][i]==1){ 37 					vector<int> del; 38 					del.push_back(current); 39 					del.push_back(i); 40 					if(fleury(edge, del)){ 41 						edge=erase(edge,del); 42 						current=i; 43 						circuit.push_back(current); 44 						cout<<current + 1<<" "; 45 						break; 46 					} 47 				} 48 			} 49 		} 50 		for(i=0; i<circuit.size(); i++){ 51 			outfile<<circuit[i] + 1<<" "; 52 		} 53 		cout<<endl<<"Chu trinh Euler da duoc ghi vao file output.txt."<<endl; 54 	}else{ 55 		cout<<"Khong tim duoc chu trinh Euler."<<endl; 56 	} 57 	system("PAUSE"); return 0; 58 } 59  60 bool euler(vector<vector<int> > edge){ 61 	for(int i=0; i<edge.size(); i++){ 62 		int deg=0; 63 		for(int j=0; j<edge[0].size(); j++){ 64 			deg+=edge[i][j]; 65 		} 66 		if(deg%2!=0){  67 			return false; 68 		} 69 	} 70 	return true; 71 } 72  73 bool fleury(vector<vector<int> > edge, vector<int> del){ 74 	int n, i, j, k; 75 	if(del[0]==del[1]){ 76 		return false; 77 	} 78 	vector<vector<int> > edged=edge; 79 	edged[del[0]][del[1]]=0; 80 	edged[del[1]][del[0]]=0; 81 	n= edged[0].size(); 82 	//Khởi tạo bảng 83 	const int infinity=1000000; 84 	vector<bool> known; 85 	for(i=0; i<n; i++){ 86 		known.push_back(false); 87 	} 88 	vector<int> d; 89 	d.push_back(0); 90 	for(i=1; i<n; i++){ 91 		d.push_back(infinity); 92 	} 93 	vector<int> p; 94 	for(i=0; i<n; i++){ 95 		p.push_back(-1); 96 	}	 97 	for(k=0; k<n; k++) 98 	{ 99 		//Tìm giá trị min của d cho đỉnh chưa biết100 		int min=0;101 		while(known[min]==true){102 			min++;103 		}104 		for(i=0; i<n; i++){105 			if(known[i]==false && d[i]<d[min]){106 				min=i;107 			}108 		}109 		//Cập nhật lại bảng110 		known[min]=true;111 		for(j=0; j<n; j++){112 			if(edged[min][j]!=0 && d[j]>edged[min][j] && known[j]==false){113 				d[j]=edged[min][j];114 				p[j]=min;115 			}116 		}117 	}118 	bool ok=true;	119 	for(i=1; i<n; i++){120 		if(p[i]==-1){121 			for (int j=0; j<n; j++){122 				if(edged[i][j]!=0){123 					ok=false; break;124 				}125 			}126 		}127 	}128 	return ok;129 }130 131 vector<vector<int> > erase(vector< vector<int> > edge, vector<int> del){132 	vector< vector<int> > edged=edge;133 	edged[del[0]][del[1]]=0;134 	edged[del[1]][del[0]]=0;135 	return edged;136 }137 138 bool empty(vector<vector<int> > edge){139 	for(int i=0; i<edge.size(); i++){140 		for(int j=0; j<edge[0].size(); j++){141 			if(edge[i][j]==1){142 				return false;143 			}144 		}145 		return true;146 	}147 }

Tập tin Output.txt:

Hình 21: Tập tin output.txt